#include<iostream>
using namespace std;
struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(const int x) :val(x), left(0), right(0){}
};
//剑指offer题17：输入两棵二叉树A,B,判断B是不是A的子结构(ps:约定空树不是任意一棵树的子结构)
bool HasSubtree(TreeNode *rootA,TreeNode *rootB)
{
	//刚进来的时候,rootA->_val一定等于rootB->_val
	if (!rootB)return true;
	
	return (rootA && rootA->val == rootB->val)
	&& HasSubtree(rootA->left, rootB->left)
	&& HasSubtree(rootA->right, rootB->right);
}
bool IsSubtree(TreeNode *rootA,TreeNode *rootB)
{
	if (!rootA || !rootB)return false;
	
	bool flag = false;
	if (rootA->val == rootB->val)
	flag = HasSubtree(rootA, rootB);
	
	return flag ? true : IsSubtree(rootA->left, rootB) || IsSubtree(rootA->right, rootB);
}
int main()
{
	TreeNode *head1 = new TreeNode(1);
	TreeNode *head2 = new TreeNode(2);
	TreeNode *head3 = new TreeNode(3);
	TreeNode *head4 = new TreeNode(4);
	TreeNode *head5 = new TreeNode(5);
	TreeNode *head6 = new TreeNode(6);
	TreeNode *head7 = new TreeNode(7);
	TreeNode *head8 = new TreeNode(8);
	head1->left = head2; head1->right = head3;//根
	head2->left = head4;//左子树
	head4->right = head7;
	head3->left = head5; head3->right = head6;//右子树
	head6->left = head8;
	
	TreeNode *cur1 = new TreeNode(2);
	TreeNode *cur2 = new TreeNode(5);
	TreeNode *cur3 = new TreeNode(6);
	cur1->left = cur2; cur1->right = cur3;
	
	cout << HasSubtree(head3, cur1) << endl;
	cout << IsSubtree(head1, cur1) << endl;
	
	return 0;
}
